// Problem 1 ----------------------------------
// If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
// Find the sum of all the multiples of 3 or 5 below 1000.

let naturals = seq { 0 .. 999 }

// Alternativa 1
let mutipleOfThree n =
    n % 3 = 0
let mutipleOfFive n =
    n % 5 = 0
let mutipleOfThreeOrFive n =
    mutipleOfThree n || mutipleOfFive n
let multiplesOfThreeOrFive sequence =
    sequence |> Seq.filter mutipleOfThreeOrFive
let sumOfMultiplesOF3And5 sequence =
    sequence |> multiplesOfThreeOrFive |> Seq.sum
let sum4 = seq { 0 .. 999 } |> sumOfMultiplesOF3And5

// Alternativa 2
let sum = seq { 0 .. 999 } |> Seq.filter (fun el -> el % 3 = 0 || el % 5 = 0 ) |> Seq.sum

// Alternativa 3
let sum2 = seq { for i in 0 .. 999 do if i % 3 = 0 || i % 5 = 0 then yield i } |> Seq.sum

// Alternativa 4
let rec sumOfMultiplesOF3And5Rec list =
    match list with
    | [] -> 0
    | h :: t when h % 3 = 0 || h % 5 = 0 -> h + sumOfMultiplesOF3And5Rec t
    | h :: t -> sumOfMultiplesOF3And5Rec t
let sum3 = sumOfMultiplesOF3And5Rec [ 0 .. 999 ]

// Per capire l'ondemand delle sequences
[| 0I .. 99999999I |] |> Array.filter (fun el -> el % 3I = 0I || el % 5I = 0I ) |> Array.sum        // Arriva in breve a 2 GB di memoria senza calcolare il risultato (System.OutOfMemoryException: Out of memory)
seq { 0I .. 99999999I } |> Seq.filter (fun el -> el % 3I = 0I || el % 5I = 0I ) |> Seq.sum          // Con 72 MB di memoria arriva al risultato


// Problem 2 ----------------------------------
// Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
// 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
// By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

let rec fibonacci n =
    match n with
    | 0 -> 0
    | n when n <= 2 -> 1
    | n -> fibonacci(n-1) + fibonacci(n-2)

List.init 34 fibonacci |> List.filter (fun el -> el % 2 = 0 ) |> List.sum


// Problem 3 ----------------------------------
// The prime factors of 13195 are 5, 7, 13 and 29.
// What is the largest prime factor of the number 600851475143 ?

// Generatore numeri primi - Metodo classico delle divisioni - NON funziona con i BigInt

/// Controlla se il numero passato come parametro è divisibile per un numero della sequenza
let rec checkDivisibility number sequence =
    match Seq.length sequence with
    | 0 -> false
    | n when (float (Seq.head sequence)) > System.Math.Sqrt (float number) -> false 
    | n when number % Seq.head sequence = 0 -> true
    | _ -> checkDivisibility number (Seq.skip 1 sequence)

/// Un metodo per verificare se un numero n è primo si definisce test di primalità. Un metodo che discende direttamente dalla definizione 
/// è controllare che non sia diviso da nessun numero minore di n o, in modo più efficiente, da nessun primo minore di n. Ad esempio, per 
/// provare che 11 è primo, basta osservare che non è diviso da 2, 3, 5 e 7 (che sono i primi minori di 11).
/// Proprietà dei numeri primi utilizzate:
///  - Il più piccolo numero primo è 2; tutti gli altri sono dispari, in quanto ogni numero pari è divisibile per 2.
///  - Se si utilizza il metodo delle divisioni per dimostrare la primalità di un numero X si può evitare di controllare la divisibilità di X per 
///      numeri maggiori della radice quadrata di X.
///          -> sqrt(600851475143) = 775146,0992
let rec classicMethod (sequence : seq<int>) (primes : seq<int>) =
    match Seq.length sequence with
    | 0 -> primes
    | _ when checkDivisibility (Seq.head sequence) primes = false -> classicMethod (Seq.skip 1 sequence) (Seq.append primes (seq [(Seq.head sequence)])) 
    | _ -> classicMethod (Seq.skip 1 sequence) primes

let primes = classicMethod (seq { for i in 3 .. 10000 do if i % 2 <> 0 then yield i }) (seq [2])
let maxPrme = primes |> Seq.filter (fun seqEl -> 600851475 % seqEl = 0 ) |> Seq.max


// Generatore numeri primi - Crivello di eratostene

let sieveGenerator divisor =
    Seq.filter ( fun el -> not (el % divisor = 0) ) 
  
let rec primesGenerator sequence sieveChain primes =
    if (sieveChain (sequence)) |> Seq.isEmpty then
        primes
    else
        let head = (Seq.head (sieveChain (sequence)))
        let primes = (Seq.append primes (seq [head]))           // l'elemento in testa ha passato la sieveChain quindi è un numero primo
        let sieveChain : (seq<int> -> seq<int>) = sieveChain >> ( sieveGenerator head )
        primesGenerator (Seq.skip 1 sequence) sieveChain primes

// Non funziona con 10000
primesGenerator ( seq { 3 .. 1000 } ) (sieveGenerator 2) (seq [2]) |> Seq.iter ( fun x -> printfn "%d" x )


//Generatore numeri primi (SOLUZIONE) - Crivello di eratostene - http://learningfsharp.blogspot.it/2010/12/project-euler-problem-3.html

open System.Collections
open System.Numerics

let getPrimesInt64 max =
  let primes = new BitArray(max+1, true)
  seq { 2 .. max } |> Seq.filter ( fun n ->
                                            if primes.[int n] then
                                              for i in bigint n * bigint n..bigint n..bigint max do primes.[int i] <- false     // Mette a "false" tutte le posizioni mutiple di "n"
                                            primes.[int n] )             // Dato che l'elemento "n" è true l'elemento viene inserito nella lista risultante     
    
let primes = getPrimesInt64 1000000

let FindLargestPrimeFactor (n:BigInteger) =
    let primes = getPrimesInt64 775146
    let filteredList = primes |> Seq.filter(fun x -> n % bigint x = 0I)
    Seq.max filteredList

let resultingPrimeFactor = FindLargestPrimeFactor 600851475143I


// Generatore numeri primi - http://stackoverflow.com/questions/5404692/prime-number-lazy-sequence

let isPrime (number : bigint) =
    seq { bigint(2) .. bigint(System.Math.Sqrt(float number))}
    |> Seq.exists (fun x -> number % x = 0I )
    |> not

let primes =
    Seq.initInfinite (fun i -> i + 2) //need to skip 0 and 1 for isPrime
    |> Seq.map (fun i -> bigint(i))
    |> Seq.filter isPrime

primes |> Seq.take 100 |> Seq.iter ( fun x -> printfn "%A" x )


// Problem 4 ----------------------------------
// A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
// Find the largest palindrome made from the product of two 3-digit numbers.

let isPalindrome (str:string) =
    let max = str.Length - 1
    let indexes = seq { for i in 0 .. max/2 -> (i, max - i) }
    let mutable res = true                                      // Devo usare "mutable" perché i loop (for e while) sono intesi per la programmazione imperativa
    for (i, j) in indexes do                                    //  e DEVONO avere un tipo di ritorno del body pari a unit
        if str.[i] <> str.[j] then
            res <- false
    res
    
//function for reversing a string
let reverse (s:string) = new string(s |> Seq.toArray |> Array.rev)
                
let maxPalindrome = seq { for i in 100 .. 999 do                            // Partiamo da 100 perché viene chiesto il numero formato dal prodotto di numeri a 3 digit
                            for j in i .. 999 do                            // Con a<=b si diminuiscono i duplicati
                                yield i*j } 
                                |> Seq.filter ( fun el -> isPalindrome (string el) )
                                |> Seq.max               





